package s03

var needSortDatas = []int{0, 1, 4, 576, 123, 9, 8, 4, 5, 2, 1, 90, 123, 1234123, 564745, 4, 5, 76, 8, 2, 3, 576, 8, 9, 87, 123, 123, 90, 90}

//归并排序，先分块，再合并 2021.10.25
func MerageSort(data []int) []int {
	dataLen := len(data)
	if dataLen == 2 { //最后了
		if data[0] > data[1] {
			return []int{data[1], data[0]}
		}
		return data
	} else if dataLen == 1 {
		return data
	}
	middleDataLen := dataLen / 2
	one := MerageSort(data[0:middleDataLen])
	two := MerageSort(data[middleDataLen:dataLen])
	oneLen := len(one)
	twoLen := len(two)
	//合并one two
	oneLast := 0
	twoLast := 0
	out := make([]int, dataLen)
	for i := range out {
		if oneLast < oneLen && twoLast < twoLen {
			if one[oneLast] < two[twoLast] {
				out[i] = one[oneLast]
				oneLast = oneLast + 1
				continue
			} else {
				out[i] = two[twoLast]
				twoLast = twoLast + 1
				continue
			}
		} else if oneLast >= oneLen { //one已经结束了
			out[i] = two[twoLast]
			twoLast = twoLast + 1
		} else if twoLast >= twoLen {
			out[i] = one[oneLast]
			oneLast = oneLast + 1
		}
	}
	return out
}

//快速排序 2021.10.26
func QuickSort(data []int) []int {
	p := 0
	r := len(data) - 1
	QuickSortC(data, p, r)
	return data
}

func QuickSortC(data []int, p, r int) {
	if p >= r {
		return
	}
	q := QuickSortPart(data, p, r)
	QuickSortC(data, p, q-1)
	QuickSortC(data, q+1, r)
}

func QuickSortPart(data []int, p, r int) int {
	point := data[r]
	i := p
	for j := p; j <= r; j++ {
		if data[j] < point {
			tmp := data[j]
			data[j] = data[i]
			data[i] = tmp
			i++
		}
	}
	data[r] = data[i]
	data[i] = point
	return i
}

//冒泡排序 2021.10.27
func MaoPaoSort(data []int) []int {
	dataLen := len(data)
	for i := 0; i < dataLen; i++ {
		out := false
		for n := 0; n < dataLen-i-1; n++ {
			if data[n] > data[n+1] {
				tmp := data[n]
				data[n] = data[n+1]
				data[n+1] = tmp
				out = true
			}
		}
		if !out {
			break
		}
	}
	return data
}

//插入排序 2021.10.28
//插入排序是插入已经排好序的
func InsertSort(data []int) []int {
	dataLen := len(data)
	for i := 1; i < dataLen; i++ {
		v := data[i]
		for c := 0; c < i; c++ {
			s := data[c]
			if v < s { //进行移位操作
				data[c] = v
				//然后从c:used => c+1:userd+1都要后移一位，这个怎么做呢
				lastValue := s
				for b := c; b < i; b++ {
					temp := data[b+1]
					data[b+1] = lastValue
					lastValue = temp
				}
				break
			}
		}
	}
	return data
}
